package com.clps.algorithm.chapter08.二叉搜索树的下一个结点;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.Stack;

/**
 * 给你一个二叉搜索时和它的一个结点p，请找出按中序遍历的顺序该结点p的下一个结点。
 * 假设二叉搜索树中结点的值都是唯一的。例如在图8.9的二叉搜索树中，结点8的下一个结点是结点9，结点11的下一个结点是null。
 */
public class dem01 {
    public static void main(String[] args) {

    }

    public TreeNode inorderSuccessor(TreeNode root,TreeNode p){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        boolean found = false;
        while (cur!=null ||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur= stack.pop();
            if(found){
                break;
            }else if(p == cur){
                found = true;
            }
            cur = cur.right;
        }
        return  cur;
    }
}
